core-attr.c

   1 /*
   2  * Copyright Neil Brown ©2015 <neil@brown.name>
   3  * May be distributed under terms of GPLv2 - see file:COPYING
   4  *
   5  * Attributes.
   6  *
   7  * Attributes are attached to text in buffers and to marks and probably
   8  * other things.
   9  * They are simply name=value pairs, stored as strings though direct
  10  * conversion to numbers and Bools is provided.
  11  * Values must be "small".  The name and value together must be less than
  12  * 512 bytes, and there is probably some padding in there.  If you get
  13  * even close to this limit you are doing something wrong.
  14  * Larger strings need to be stored elsewhere with some sort of indirect.
  15  * (Hmmm.. this excludes file names - is that a good idea?)
  16  *
  17  * Attributes are stored in a list sorted by attribute name.  Strings
  18  * of digits in the name sort like the number they represent, so "6hello"
  19  * comes before "10world".  When such a number compares against a single
  20  * non-digit character the char comes first.
  21  *
  22  * Attributes for text are stored in one list for a section of text.
  23  * Each attribute is prefixed by the offset where the attribute applies.
  24  *
  25  * The offsets are really byte offsets - the text is utf-8.
  26  *
  27  * When attributes are stored on non-text objects they don't have
  28  * a number prefix.
  29  *
  30  */
  31
  32 #include <stdlib.h>
  33 #include <malloc.h>
  34 #include <string.h>
  35 #include <ctype.h>
  36
  37 struct attrset {
  38         unsigned short  size, /* space allocated */
  39                         len;  /* space used */
  40         struct attrset *next;
  41         char            attrs[0];
  42 };
  43
  44 #if defined(TEST_ATTR_ADD_DEL)
  45 #define MAX_ATTR_SIZE (64 - sizeof(struct attrset))
  46 #else
  47 #define MAX_ATTR_SIZE (512 - sizeof(struct attrset))
  48 #endif
  49
  50 static struct attrset *newattr(struct attrset *old, int size)
  51 {
  52         struct attrset *set = realloc(old, sizeof(struct attrset) + size);
  53         set->size = size;
  54         if (old == NULL) {
  55                 set->len = 0;
  56                 set->next = NULL;
  57         }
  58         return set;
  59 }
  60
  61 /* attr_cmp just deals with bytes and ASCII digits, so it is
  62  * not aware for wchars
  63  */
  64 static int getcmptok(char **ap)
  65 {
  66         char *a = *ap;
  67         char c = *a++;
  68         int i;
  69         if (!isdigit(c)) {
  70                 *ap = a;
  71                 return c;
  72         }
  73         i = c - '0';
  74         while (isdigit(*a)) {
  75                 c = *a++;
  76                 i = i*10 + (c - '0');
  77         }
  78         *ap = a;
  79         return i+256;
  80 }
  81
  82 /* Compare 'a' and 'b' treating strings of digits as numbers.
  83  * If bnum >= 0, it is used as a leading number on 'b'.
  84  */
  85 static int attr_cmp(char *a, char *b, int bnum)
  86 {
  87         while (*a && *b) {
  88                 int ai, bi;
  89                 ai = getcmptok(&a);
  90                 if (bnum >= 0) {
  91                         bi = bnum + 256;
  92                         bnum = -1;
  93                         if (*a == ' ')
  94                                 a++;
  95                 } else
  96                         bi = getcmptok(&b);
  97                 if (ai < bi)
  98                         return -1;
  99                 if (ai > bi)
 100                         return 1;
 101         }
 102         if (*a)
 103                 return 1;
 104         if (*b)
 105                 return -1;
 106         return 0;
 107 }
 108
 109 #ifdef TEST_ATTR_CMP
 110 #include <stdlib.h>
 111 #include <stdio.h>
 112 struct {char *a, *b; int result;} test[] = {
 113         { "hello", "there", -1},
 114         { "6hello", "10world", -1},
 115         { "0005six", "5six", 0},
 116         { "ab56", "abc", 1},
 117 };
 118 int main(int argc, char *argv[])
 119 {
 120         int i;
 121         int rv = 0;
 122         for (i = 0; i < sizeof(test)/sizeof(test[0]); i++) {
 123                 if (attr_cmp(test[i].a, test[i].b, -1) == test[i].result)
 124                         printf("%s <-> %s = %d OK\n",
 125                                test[i].a, test[i].b, test[i].result);
 126                 else {
 127                         printf("%s <-> %s = %d, not %d\n",
 128                                test[i].a, test[i].b, attr_cmp(test[i].a,
 129                                                               test[i].b, -1),
 130                                test[i].result);
 131                         rv = 1;
 132                 }
 133         }
 134         exit(rv);
 135 }
 136
 137 #endif
 138
 139 int __attr_find(struct attrset ***setpp, char *key, int *offsetp, int keynum)
 140 {
 141         struct attrset **setp = *setpp;
 142         struct attrset *set = *setp;
 143         int i;
 144
 145         if (!set)
 146                 return -1;
 147         *offsetp = 0;
 148         while (set->next &&
 149                attr_cmp(set->next->attrs, key, keynum) <= 0) {
 150                 setp = &set->next;
 151                 set = *setp;
 152         }
 153         *setpp = setp;
 154
 155         for (i = 0; i < set->len; ) {
 156                 int cmp = attr_cmp(set->attrs + i, key, keynum);
 157                 if (cmp >= 0) {
 158                         *offsetp = i;
 159                         *setpp = setp;
 160                         return cmp;
 161                 }
 162                 i += strlen(set->attrs + i) + 1;
 163                 i += strlen(set->attrs + i) + 1;
 164         }
 165         *offsetp = i;
 166         return 1;
 167 }
 168
 169 int attr_del(struct attrset **setp, char *key)
 170 {
 171         int offset = 0;
 172         int cmp;
 173         int len;
 174         struct attrset *set;
 175
 176         cmp = __attr_find(&setp, key, &offset, -1);
 177
 178         if (cmp)
 179                 /* Not found */
 180                 return 0;
 181         set = *setp;
 182         len = strlen(set->attrs + offset) + 1;
 183         len += strlen(set->attrs + offset + len) + 1;
 184         memmove(set->attrs + offset,
 185                 set->attrs + offset + len,
 186                 set->len - (offset + len));
 187         set->len -= len;
 188         if (set->len == 0) {
 189                 *setp = set->next;
 190                 free(set);
 191         }
 192         return 1;
 193 }
 194
 195 char *attr_get_str(struct attrset *set, char *key, int keynum)
 196 {
 197         struct attrset **setp = &set;
 198         int offset = 0;
 199         int cmp = __attr_find(&setp, key, &offset, keynum);
 200
 201         if (cmp != 0)
 202                 return NULL;
 203         set = *setp;
 204         offset += strlen(set->attrs + offset) + 1;
 205         return set->attrs + offset;
 206 }
 207
 208 char *attr_find(struct attrset *set, char *key)
 209 {
 210         return attr_get_str(set, key, -1);
 211 }
 212
 213 int attr_set_str(struct attrset **setp, char *key, char *val, int keynum)
 214 {
 215         int offset = 0;
 216         int cmp;
 217         struct attrset *set;
 218         unsigned int len;
 219         char nkey[22];
 220         int nkeylen = 0;
 221
 222         cmp = __attr_find(&setp, key, &offset, keynum);
 223
 224         if (cmp == 0) {
 225                 /* Remove old value */
 226                 set = *setp;
 227                 len = strlen(set->attrs + offset) + 1;
 228                 len += strlen(set->attrs + offset + len) + 1;
 229                 memmove(set->attrs + offset,
 230                         set->attrs + offset + len,
 231                         set->len - (offset + len));
 232                 set->len -= len;
 233         }
 234         if (!val)
 235                 return cmp;
 236         set = *setp;
 237         if (keynum >= 0) {
 238                 snprintf(nkey, sizeof(nkey), "%d ", keynum);
 239                 nkeylen = strlen(nkey);
 240         }
 241         len = nkeylen + strlen(key) + 1 + strlen(val) + 1;
 242         if (set == NULL || set->len + len > set->size) {
 243                 /* Need to re-alloc or alloc new */
 244                 if (!set) {
 245                         set = newattr(NULL, len);
 246                         *setp = set;
 247                 } else if (set->len + len <= MAX_ATTR_SIZE) {
 248                         /* Just make this block bigger */
 249                         set = newattr(set, set->len + len);
 250                         *setp = set;
 251                 } else if (offset + len <= MAX_ATTR_SIZE) {
 252                         /* split following entries in separate block */
 253                         struct attrset *new = newattr(NULL, set->len - offset);
 254
 255                         new->next = set->next;
 256                         set->next = new;
 257                         new->len = set->len - offset;
 258                         set->len = offset;
 259                         memcpy(new->attrs, set->attrs + offset,
 260                                new->len);
 261                 } else {
 262                         /* Split follow in entries and store new entry there */
 263                         struct attrset *new = newattr(NULL, set->len - offset + len);
 264
 265                         new->next = set->next;
 266                         set->next = new;
 267                         new->len = set->len - offset;
 268                         set->len = offset;
 269                         memcpy(new->attrs, set->attrs + offset,
 270                                new->len);
 271                         set = new;
 272                         offset = 0;
 273                 }
 274         }
 275         memmove(set->attrs + offset + len, set->attrs + offset, set->len - offset);
 276         strncpy(set->attrs + offset, nkey, nkeylen);
 277         strcpy(set->attrs + offset + nkeylen, key);
 278         strcpy(set->attrs + offset + nkeylen + strlen(key) + 1, val);
 279         set->len += len;
 280         return cmp;
 281 }
 282
 283 #if defined(TEST_ATTR_ADD_DEL) || defined(TEST_ATTR_TRIM)
 284 void attr_dump(struct attrset *set)
 285 {
 286         printf("DUMP ATTRS:\n");
 287         while (set) {
 288                 int i;
 289                 printf(" %d of %d:\n", set->len, set->size);
 290                 for (i = 0; i < set->len; ) {
 291                         printf("  %3d: \"%s\"", i, set->attrs + i);
 292                         i += strlen(set->attrs+i) + 1;
 293                         printf(" -> \"%s\"\n", set->attrs + i);
 294                         i += strlen(set->attrs+i) + 1;
 295                 }
 296                 set = set->next;
 297         }
 298         printf("END DUMP\n");
 299 }
 300 #endif
 301
 302 #ifdef TEST_ATTR_ADD_DEL
 303 enum act { Add, Remove, Find };
 304 struct action {
 305         enum act act;
 306         char *key;
 307         char *val;
 308 } actions[] = {
 309         { Add, "Hello", "world"},
 310         { Add, "05 Foo", "Bar" },
 311         { Add, "1 Bold", "off" },
 312         { Add, "9 Underline", "on" },
 313         { Remove, "Hello", NULL },
 314         { Find, "5 Foo", "Bar" },
 315         { Add, "20 Thing", "Stuff" },
 316         { Add, "01 Bold", "on" },
 317         { Add, "1 StrikeThrough", "no" },
 318         { Add, "2 StrikeThrough", "no" },
 319         { Find, "1 StrikeThrough", "no" },
 320         { Find, "5 Foo", "Bar" },
 321         { Add, "1 Nextthing", "nonono" },
 322 };
 323
 324 int main(int argc, char *argv[])
 325 {
 326         int i;
 327         int rv = 0;
 328         struct attrset *set = NULL;
 329         for (i = 0; i < sizeof(actions)/sizeof(actions[0]); i++) {
 330                 struct action *a = &actions[i];
 331                 char *v;
 332                 switch(a->act) {
 333                 case Add:
 334                         attr_set_str(&set, a->key, a->val, -1); continue;
 335                 case Remove:
 336                         if (attr_del(&set, a->key) == 0) {
 337                                 printf("Action %d: Remove %s: failed\n",
 338                                        i, a->key);
 339                                 rv = 1;
 340                                 break;
 341                         }
 342                         continue;
 343                 case Find:
 344                         v = attr_find(set, a->key);
 345                         if (!v || strcmp(v, a->val) != 0) {
 346                                 printf("Action %d: Find %s: Found %s\n",
 347                                        i, a->key, v);
 348                                 rv = 1;
 349                                 break;
 350                         }
 351                         continue;
 352                 }
 353                 break;
 354         }
 355         attr_dump(set);
 356         exit(rv);
 357 }
 358 #endif
 359
 360 /* Have versions that take and return numbers, '-1' for 'not found' */
 361 int attr_find_int(struct attrset *set, char *key)
 362 {
 363         char *val = attr_find(set, key);
 364         unsigned long rv;
 365         char *end;
 366
 367         if (!val)
 368                 return -1;
 369         rv = strtoul(val, &end, 10);
 370         if (end == val || *end)
 371                 return -1;
 372         return rv;
 373 }
 374
 375 int attr_set_int(struct attrset **setp, char *key, int val)
 376 {
 377         char sval[22];
 378
 379         sprintf(sval, "%d", val);
 380         return attr_set_str(setp, key, sval, -1);
 381 }
 382
 383 #ifdef TEST_ATTR_INT
 384 int main(int argc, char *argv[])
 385 {
 386         struct attrset *set = NULL;
 387
 388         attr_set_int(&set, "One", 1);
 389         attr_set_int(&set, "Twelve", 12);
 390         attr_set_int(&set, "Four", 4);
 391         if (attr_find_int(set, "One") +
 392             attr_find_int(set, "Twelve") +
 393             attr_find_int(set, "Four")
 394             != 17) {
 395                 printf("Didn't find One, Twelve, Four\n");
 396                 exit(2);
 397         }
 398         if (attr_find_int(set, "Three") != -1) {
 399                 printf("Surprisingly found Three\n");
 400                 exit(2);
 401         }
 402         exit(0);
 403 }
 404 #endif
 405
 406 void attr_free(struct attrset **setp)
 407 {
 408         struct attrset *set = *setp;
 409         *setp = NULL;
 410         while (set) {
 411                 struct attrset *next = set->next;
 412                 free(set);
 413                 set = next;
 414         }
 415 }
 416
 417 /*
 418  * When attributes are attached to a section of text,
 419  * we might want to split the text and so split the attributes.
 420  * So:
 421  * 1- 'trim' all attributes beyond a given key
 422  * 2- copy attributes, subtracting some number from the offset.
 423  *     At offset '0', an empty value deletes the key.
 424  */
 425
 426 void attr_trim(struct attrset **setp, int nkey)
 427 {
 428         char key[22];
 429         int offset;
 430         struct attrset *set;
 431
 432         sprintf(key, "%d", nkey);
 433         __attr_find(&setp, key, &offset, 0);
 434         set = *setp;
 435         if (!set)
 436                 return;
 437         set->len = offset;
 438         if (offset)
 439                 setp = &set->next;
 440         attr_free(setp);
 441 }
 442
 443 struct attrset *attr_copy_tail(struct attrset *set, int nkey)
 444 {
 445         struct attrset *newset = NULL;
 446
 447         for (; set ; set = set->next) {
 448                 int i;
 449                 for (i = 0; i < set->len; ) {
 450                         char *k, *v;
 451                         int n;
 452                         k = set->attrs + i;
 453                         i += strlen(k) + 1;
 454                         v = set->attrs + i;
 455                         i += strlen(v) + 1;
 456                         n = atoi(k);
 457
 458                         if (n <= nkey && *v == '\0')
 459                                 v = NULL;
 460                         attr_set_str(&newset, k, v, nkey);
 461                 }
 462         }
 463
 464         return newset;
 465 }
 466
 467 /* Collect the attributes in effect at a given pos and return
 468  * a new set with the new alternate numeric prefix, or nothing if '-1'
 469  */
 470 struct attrset *attr_collect(struct attrset *set, unsigned int pos,
 471                              int prefix)
 472 {
 473         struct attrset *newset = NULL;
 474         char kbuf[512];
 475
 476         for (; set ; set = set->next) {
 477                 int i;
 478                 for (i = 0; i < set->len; ) {
 479                         char *k, *v, *e;
 480                         unsigned long n;
 481                         k = set->attrs + i;
 482                         i += strlen(k) + 1;
 483                         v = set->attrs + i;
 484                         i += strlen(v) + 1;
 485                         n = strtoul(k, &e, 10);
 486
 487                         if (n > pos)
 488                                 goto done;
 489                         while (*e == ' ')
 490                                 e++;
 491                         if (prefix >= 0) {
 492                                 snprintf(kbuf, 512, "%d %s", prefix, e);
 493                                 e = kbuf;
 494                         }
 495                         if (*v == '\0')
 496                                 v = NULL;
 497                         attr_set_str(&newset, e, v, -1);
 498                 }
 499         }
 500 done:
 501         return newset;
 502 }
 503
 504 #ifdef TEST_ATTR_TRIM
 505
 506 char *keys[] = {
 507         "1 Bold", "2 Bold", "5 Bold", "10 Bold",
 508         "0 Colour", "3 Colour", "08 Colour", "12 Colour",
 509         "2 Invis", "4 Invis", "6 Invis", "9 Invis",
 510 };
 511
 512 int main(int argc, char *argv[])
 513 {
 514         int i;
 515         struct attrset *set = NULL;
 516         struct attrset *newset, *new2;
 517
 518         for (i = 0; i < sizeof(keys)/sizeof(keys[0]); i++)
 519                 attr_set_str(&set, keys[i], keys[i], -1);
 520
 521         newset = attr_copy_tail(set, 5);
 522         attr_trim(&set, 5);
 523         new2 = attr_collect(newset, 9, 4);
 524         attr_dump(set);
 525         attr_dump(newset);
 526         attr_dump(new2);
 527         exit(0);
 528 }
 529 #endif
 530
 531 /*
 532 Iterator for set.
 533 */