core-attr.c

   1 /*
   2  * Copyright Neil Brown ©2015-2020 <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 #include "core.h"
  37
  38 struct attrset {
  39         unsigned short  size, /* space allocated */
  40                         len;  /* space used */
  41         struct attrset *next;
  42         char            attrs[0];
  43 };
  44
  45 /* NOTE: this MAX is the largest sized allocation which
  46  * can be shared by multiple attrs.  The size is the sum
  47  * of keys and values including nul terminator.
  48  * If an attr is larger, it gets an attrset all of its own.
  49  */
  50 #if defined(TEST_ATTR_ADD_DEL)
  51 #define MAX_ATTR_SIZE (64 - sizeof(struct attrset))
  52 #else
  53 #define MAX_ATTR_SIZE (512 - sizeof(struct attrset))
  54 #endif
  55
  56 static struct attrset *safe newattr(struct attrset *old, int size)
  57 {
  58         struct attrset *set = realloc(old, sizeof(struct attrset) + size);
  59         set->size = size;
  60         if (old == NULL) {
  61                 set->len = 0;
  62                 set->next = NULL;
  63         }
  64         return set;
  65 }
  66
  67 /* attr_cmp just deals with bytes and ASCII digits, so it is
  68  * not aware for wchars
  69  */
  70 static int getcmptok(const char **ap safe)
  71 {
  72         const char *a safe;
  73         char c;
  74         int i;
  75
  76         if (!*ap)
  77                 /* FIXME smatch should handle "char * safe *ap safe" */
  78                 return 0;
  79         a = *ap;
  80         c = *a++;
  81         if (!isdigit(c)) {
  82                 *ap = a;
  83                 return c;
  84         }
  85         i = c - '0';
  86         while (isdigit(*a)) {
  87                 c = *a++;
  88                 i = i*10 + (c - '0');
  89         }
  90         *ap = a;
  91         return i+256;
  92 }
  93
  94 /* Compare 'a' and 'b' treating strings of digits as numbers.
  95  * If bnum >= 0, it is used as a leading number on 'b'.
  96  */
  97 static int attr_cmp(const char *a safe, const char *b safe, int bnum)
  98 {
  99         while (*a && (*b || bnum >= 0)) {
 100                 int ai, bi;
 101                 ai = getcmptok(&a);
 102                 if (bnum >= 0) {
 103                         bi = bnum + 256;
 104                         bnum = -1;
 105                         if (*a == ' ')
 106                                 a++;
 107                 } else
 108                         bi = getcmptok(&b);
 109                 if (ai < bi)
 110                         return -1;
 111                 if (ai > bi)
 112                         return 1;
 113         }
 114         if (*a)
 115                 return 1;
 116         if (*b)
 117                 return -1;
 118         return 0;
 119 }
 120
 121 #ifdef TEST_ATTR_CMP
 122 #include <stdlib.h>
 123 #include <stdio.h>
 124 struct {const char *a, *b; int result;} test[] = {
 125         { "hello", "there", -1},
 126         { "6hello", "10world", -1},
 127         { "0005six", "5six", 0},
 128         { "ab56", "abc", 1},
 129 };
 130 int main(int argc, char *argv[])
 131 {
 132         int i;
 133         int rv = 0;
 134         for (i = 0; i < sizeof(test)/sizeof(test[0]); i++) {
 135                 if (attr_cmp(test[i].a, test[i].b, -1) == test[i].result)
 136                         printf("%s <-> %s = %d OK\n",
 137                                test[i].a, test[i].b, test[i].result);
 138                 else {
 139                         printf("%s <-> %s = %d, not %d\n",
 140                                test[i].a, test[i].b, attr_cmp(test[i].a,
 141                                                               test[i].b, -1),
 142                                test[i].result);
 143                         rv = 1;
 144                 }
 145         }
 146         exit(rv);
 147 }
 148
 149 #endif
 150
 151 static int __attr_find(struct attrset ***setpp safe, const char *key safe,
 152                        int *offsetp safe, int keynum)
 153 {
 154         struct attrset **setp safe;
 155         struct attrset *set;
 156         int i;
 157
 158         if (!*setpp)
 159                 /* FIXME smatch should check this */
 160                 return -1;
 161         setp = *setpp;
 162         set = *setp;
 163         if (!set)
 164                 return -1;
 165         *offsetp = 0;
 166         while (set->next &&
 167                attr_cmp(set->next->attrs, key, keynum) <= 0) {
 168                 setp = &set->next;
 169                 set = *setp;
 170         }
 171         *setpp = setp;
 172
 173         for (i = 0; i < set->len; ) {
 174                 int cmp = attr_cmp(set->attrs + i, key, keynum);
 175                 if (cmp >= 0) {
 176                         *offsetp = i;
 177                         *setpp = setp;
 178                         return cmp;
 179                 }
 180                 i += strlen(set->attrs + i) + 1;
 181                 i += strlen(set->attrs + i) + 1;
 182         }
 183         *offsetp = i;
 184         return 1;
 185 }
 186
 187 static void do_del(struct attrset * *setp safe, int offset)
 188 {
 189         int len;
 190         struct attrset *set;
 191
 192         set = safe_cast *setp;
 193         len = strlen(set->attrs + offset) + 1;
 194         len += strlen(set->attrs + offset + len) + 1;
 195         memmove(set->attrs + offset,
 196                 set->attrs + offset + len,
 197                 set->len - (offset + len));
 198         set->len -= len;
 199         if (set->len == 0) {
 200                 *setp = set->next;
 201                 free(set);
 202         }
 203 }
 204
 205 bool attr_del(struct attrset * *setp safe, const char *key safe)
 206 {
 207         int offset = 0;
 208         int cmp;
 209
 210         cmp = __attr_find(&setp, key, &offset, -1);
 211
 212         if (cmp)
 213                 /* Not found */
 214                 return False;
 215         do_del(setp, offset);
 216         return True;
 217 }
 218
 219 void attr_del_all(struct attrset * *setp safe, const char *key safe,
 220                   int low, int high)
 221 {
 222         int offset = 0;
 223         /* Delete all attrs 'key' with keynum from 'low' to 'high' */
 224         while (low <= high) {
 225                 struct attrset *set;
 226                 int n;
 227                 int cmp = __attr_find(&setp, key, &offset, low);
 228
 229                 if (cmp < 0)
 230                         /* Nothing more to find */
 231                         return;
 232                 low += 1;
 233                 if (cmp == 0) {
 234                         /* Found, better delete */
 235                         do_del(setp, offset);
 236                         continue;
 237                 }
 238                 /* found something higher, possibly update 'low'
 239                  * to skip over gaps.
 240                  */
 241                 set = *setp;
 242                 if (!set || offset >= set->len)
 243                         continue;
 244                 n = atoi(set->attrs + offset);
 245                 if (n > low)
 246                         low = n;
 247         }
 248 }
 249
 250 char *attr_get_str(struct attrset *set, const char *key safe, int keynum)
 251 {
 252         struct attrset **setp = &set;
 253         int offset = 0;
 254         int cmp = __attr_find(&setp, key, &offset, keynum);
 255
 256         if (cmp != 0 || !*setp)
 257                 return NULL;
 258         set = *setp;
 259         offset += strlen(set->attrs + offset) + 1;
 260         return set->attrs + offset;
 261 }
 262
 263 char *attr_find(struct attrset *set, const char *key safe)
 264 {
 265         return attr_get_str(set, key, -1);
 266 }
 267
 268 const char *attr_get_next_key(struct attrset *set, const char *key safe,
 269                               int keynum, const char **valp safe)
 270 {
 271         struct attrset **setp = &set;
 272         int offset = 0;
 273         int cmp = __attr_find(&setp, key, &offset, keynum);
 274         const char *val;
 275
 276         if (cmp < 0)
 277                 return NULL;
 278         set = safe_cast *setp;
 279         if (cmp == 0) {
 280                 /* Skip the matching key, then value */
 281                 offset += strlen(set->attrs + offset) + 1;
 282                 offset += strlen(set->attrs + offset) + 1;
 283         }
 284         if (offset >= set->len) {
 285                 set = set->next;
 286                 offset = 0;
 287         }
 288         if (!set)
 289                 return NULL;
 290         key = set->attrs + offset;
 291         val = key + strlen(key) + 1;
 292         if (keynum >= 0) {
 293                 int kn = getcmptok(&key);
 294                 if (kn != keynum + 256)
 295                         return NULL;
 296                 if (*key == ' ')
 297                         key += 1;
 298         }
 299         *valp = val;
 300         return key;
 301 }
 302
 303 int attr_set_str_key(struct attrset **setp safe,
 304                      const char *key safe, const char *val,
 305                      int keynum)
 306 {
 307         int offset = 0;
 308         int cmp;
 309         struct attrset *set;
 310         unsigned int len;
 311         char nkey[22];
 312         int nkeylen = 0;
 313
 314         cmp = __attr_find(&setp, key, &offset, keynum);
 315
 316         if (cmp == 0)
 317                 /* Remove old value */
 318                 do_del(setp, offset);
 319
 320         if (!val)
 321                 return cmp;
 322
 323         set = *setp;
 324         if (keynum >= 0) {
 325                 snprintf(nkey, sizeof(nkey), "%d ", keynum);
 326                 nkeylen = strlen(nkey);
 327         } else
 328                 nkey[0] = 0;
 329         len = nkeylen + strlen(key) + 1 + strlen(val) + 1;
 330         while (set == NULL || set->len + len > set->size) {
 331                 /* Need to re-alloc or alloc new */
 332                 if (!set || (offset == 0 && len + set->len > MAX_ATTR_SIZE)) {
 333                         /* Create a new set - which may exceed MAX_ATTR_SIZE */
 334                         struct attrset *new = newattr(NULL, len);
 335                         new->next = set;
 336                         *setp = new;
 337                         set = new;
 338                 } else if (set->len + len <= MAX_ATTR_SIZE) {
 339                         /* Just make this block bigger */
 340                         set = newattr(set, set->len + len);
 341                         *setp = set;
 342                 } else if (offset + len <= MAX_ATTR_SIZE) {
 343                         /* split following entries in separate block */
 344                         struct attrset *new = newattr(NULL, set->len - offset);
 345                         new->next = set->next;
 346                         set->next = new;
 347                         new->len = set->len - offset;
 348                         set->len = offset;
 349                         memcpy(new->attrs, set->attrs + offset,
 350                                new->len);
 351                 } else {
 352                         /* offset must be > 0.
 353                          * Split off following entries and try again there.
 354                          */
 355                         struct attrset *new = newattr(NULL,
 356                                                       set->len - offset);
 357
 358                         new->next = set->next;
 359                         set->next = new;
 360                         new->len = set->len - offset;
 361                         set->len = offset;
 362                         memcpy(new->attrs, set->attrs + offset,
 363                                new->len);
 364                         setp = &set->next;
 365                         set = new;
 366                         offset = 0;
 367                 }
 368         }
 369         memmove(set->attrs + offset + len, set->attrs + offset,
 370                 set->len - offset);
 371 #pragma GCC diagnostic push
 372 // GCC really doesn't like the games I"m playing here.
 373 #pragma GCC diagnostic ignored "-Wstringop-overflow"
 374         strcpy(set->attrs + offset, nkey);
 375         strcpy(set->attrs + offset + nkeylen, key);
 376         strcpy(set->attrs + offset + nkeylen + strlen(key) + 1, val);
 377 #pragma GCC diagnostic pop
 378         set->len += len;
 379         return cmp;
 380 }
 381
 382 int attr_set_str(struct attrset **setp safe,
 383                  const char *key safe, const char *val)
 384 {
 385         return attr_set_str_key(setp, key, val, -1);
 386 }
 387
 388 #if defined(TEST_ATTR_ADD_DEL) || defined(TEST_ATTR_TRIM)
 389 void attr_dump(struct attrset *set)
 390 {
 391         printf("DUMP ATTRS:\n");
 392         while (set) {
 393                 int i;
 394                 printf(" %d of %d:\n", set->len, set->size);
 395                 for (i = 0; i < set->len; ) {
 396                         printf("  %3d: \"%s\"", i, set->attrs + i);
 397                         i += strlen(set->attrs+i) + 1;
 398                         printf(" -> \"%s\"\n", set->attrs + i);
 399                         i += strlen(set->attrs+i) + 1;
 400                 }
 401                 set = set->next;
 402         }
 403         printf("END DUMP\n");
 404 }
 405 #endif
 406
 407 #ifdef TEST_ATTR_ADD_DEL
 408 enum act { Add, Remove, Find };
 409 struct action {
 410         enum act act;
 411         char *key;
 412         char *val;
 413 } actions[] = {
 414         { Add, "Hello", "world"},
 415         { Add, "05 Foo", "Bar" },
 416         { Add, "1 Bold", "off" },
 417         { Add, "9 Underline", "on" },
 418         { Remove, "Hello", NULL },
 419         { Find, "5 Foo", "Bar" },
 420         { Add, "20 Thing", "Stuff" },
 421         { Add, "01 Bold", "on" },
 422         { Add, "1 StrikeThrough", "no" },
 423         { Add, "2 StrikeThrough", "no" },
 424         { Find, "1 StrikeThrough", "no" },
 425         { Find, "5 Foo", "Bar" },
 426         { Add, "1 Nextthing", "nonono" },
 427 };
 428
 429 int main(int argc, char *argv[])
 430 {
 431         int i;
 432         int rv = 0;
 433         struct attrset *set = NULL;
 434         for (i = 0; i < sizeof(actions)/sizeof(actions[0]); i++) {
 435                 struct action *a = &actions[i];
 436                 char *v;
 437                 switch(a->act) {
 438                 case Add:
 439                         attr_set_str(&set, a->key, a->val); continue;
 440                 case Remove:
 441                         if (!attr_del(&set, a->key)) {
 442                                 printf("Action %d: Remove %s: failed\n",
 443                                        i, a->key);
 444                                 rv = 1;
 445                                 break;
 446                         }
 447                         continue;
 448                 case Find:
 449                         v = attr_find(set, a->key);
 450                         if (!v || strcmp(v, a->val) != 0) {
 451                                 printf("Action %d: Find %s: Found %s\n",
 452                                        i, a->key, v);
 453                                 rv = 1;
 454                                 break;
 455                         }
 456                         continue;
 457                 }
 458                 break;
 459         }
 460         attr_dump(set);
 461         exit(rv);
 462 }
 463 #endif
 464
 465 /* Have versions that take and return numbers, '-1' for 'not found' */
 466 int attr_find_int(struct attrset *set, const char *key safe)
 467 {
 468         const char *val = attr_find(set, key);
 469         unsigned long rv;
 470         char *end;
 471
 472         if (!val)
 473                 return -1;
 474         rv = strtoul(val, &end, 10);
 475         if (!end || end == val || *end)
 476                 return -1;
 477         return rv;
 478 }
 479
 480 int attr_set_int(struct attrset **setp safe, const char *key safe, int val)
 481 {
 482         /* 3 digits per bytes, +1 for sign and +1 for trailing nul */
 483         char sval[sizeof(int)*3+2];
 484
 485         snprintf(sval, sizeof(sval), "%d", val);
 486         return attr_set_str(setp, key, sval);
 487 }
 488
 489 #ifdef TEST_ATTR_INT
 490 int main(int argc, char *argv[])
 491 {
 492         struct attrset *set = NULL;
 493
 494         attr_set_int(&set, "One", 1);
 495         attr_set_int(&set, "Twelve", 12);
 496         attr_set_int(&set, "Four", 4);
 497         if (attr_find_int(set, "One") +
 498             attr_find_int(set, "Twelve") +
 499             attr_find_int(set, "Four")
 500             != 17) {
 501                 printf("Didn't find One, Twelve, Four\n");
 502                 exit(2);
 503         }
 504         if (attr_find_int(set, "Three") != -1) {
 505                 printf("Surprisingly found Three\n");
 506                 exit(2);
 507         }
 508         exit(0);
 509 }
 510 #endif
 511
 512 void attr_free(struct attrset **setp safe)
 513 {
 514         struct attrset *set = *setp;
 515         *setp = NULL;
 516         while (set) {
 517                 struct attrset *next = set->next;
 518                 free(set);
 519                 set = next;
 520         }
 521 }
 522
 523 /*
 524  * When attributes are attached to a section of text,
 525  * we might want to split the text and so split the attributes.
 526  * So:
 527  * 1- 'trim' all attributes beyond a given key
 528  * 2- copy attributes, subtracting some number from the offset.
 529  *     At offset '0', an empty value deletes the key.
 530  */
 531
 532 void attr_trim(struct attrset **setp safe, int nkey)
 533 {
 534         int offset;
 535         struct attrset *set;
 536
 537         __attr_find(&setp, "", &offset, nkey);
 538         set = *setp;
 539         if (!set)
 540                 return;
 541         set->len = offset;
 542         if (offset)
 543                 setp = &set->next;
 544         attr_free(setp);
 545 }
 546
 547 /* make a copy of 'set', keeping only attributes from 'nkey'
 548  * onwards.
 549  */
 550 struct attrset *attr_copy_tail(struct attrset *set, int nkey)
 551 {
 552         struct attrset *newset = NULL;
 553
 554         for (; set ; set = set->next) {
 555                 int i;
 556                 for (i = 0; i < set->len; ) {
 557                         char *k, *v;
 558                         int n;
 559                         k = set->attrs + i;
 560                         i += strlen(k) + 1;
 561                         v = set->attrs + i;
 562                         i += strlen(v) + 1;
 563                         n = atoi(k);
 564                         if (n < nkey)
 565                                 continue;
 566                         while (*k && *k != ' ')
 567                                 k++;
 568                         if (*k == ' ')
 569                                 k++;
 570
 571                         attr_set_str_key(&newset, k, v, n);
 572                 }
 573         }
 574
 575         return newset;
 576 }
 577
 578 /* Collect the attributes in effect at a given pos and return
 579  * a new set with the new alternate numeric prefix, or nothing if '-1'
 580  */
 581 struct attrset *attr_collect(struct attrset *set, unsigned int pos,
 582                              int prefix)
 583 {
 584         struct attrset *newset = NULL;
 585         char kbuf[512];
 586
 587         for (; set ; set = set->next) {
 588                 int i;
 589                 for (i = 0; i < set->len; ) {
 590                         char *k, *v, *e;
 591                         unsigned long n;
 592                         k = set->attrs + i;
 593                         i += strlen(k) + 1;
 594                         v = set->attrs + i;
 595                         i += strlen(v) + 1;
 596                         n = strtoul(k, &e, 10);
 597
 598                         if (n > pos)
 599                                 goto done;
 600                         /* FIXME shouldn't need to test 'e' */
 601                         while (e && *e == ' ')
 602                                 e++;
 603                         if (prefix >= 0) {
 604                                 snprintf(kbuf, 512, "%d %s", prefix, e);
 605                                 e = kbuf;
 606                         }
 607                         if (*v == '\0')
 608                                 v = NULL;
 609                         if (!e) e = "FIXME";
 610                         attr_set_str(&newset, e, v);
 611                 }
 612         }
 613 done:
 614         return newset;
 615 }
 616
 617 #ifdef TEST_ATTR_TRIM
 618
 619 char *keys[] = {
 620         "1 Bold", "2 Bold", "5 Bold", "10 Bold",
 621         "0 Colour", "3 Colour", "08 Colour", "12 Colour",
 622         "2 Invis", "4 Invis", "6 Invis", "9 Invis",
 623 };
 624
 625 int main(int argc, char *argv[])
 626 {
 627         int i;
 628         struct attrset *set = NULL;
 629         struct attrset *newset, *new2;
 630
 631         for (i = 0; i < sizeof(keys)/sizeof(keys[0]); i++)
 632                 attr_set_str(&set, keys[i], keys[i], -1);
 633
 634         newset = attr_copy_tail(set, 5);
 635         attr_trim(&set, 5);
 636         new2 = attr_collect(newset, 9, 4);
 637         attr_dump(set);
 638         attr_dump(newset);
 639         attr_dump(new2);
 640         exit(0);
 641 }
 642 #endif
 643
 644 /*
 645  * Iterator for set.
 646  */